Security enhancements and performance accelerations for computational devices are described in Applicant's U.S. Pat. No. 5,742,530, hereinafter “P1”, U.S. Pat. Nos. 5,513,133, 5,448,639, 5,261,001; and 5,206,824 and published PCT patent application PCT/IL98/00148 (WO98/50851); and corresponding U.S. patent application Ser. No. 09/050958, hereinafter “P2”, Onyszchuk et al's U.S. Pat. No. 4,745,568; Omura et al's U.S. Pat. No. 4,5877,627, and applicant's U.S. patent application Ser. No. 09/480,102; the disclosures of which are hereby incorporated by reference. Applicant's U.S. Pat. No. 5,206,824 shows an early apparatus operative to implement polynomial based multiplication and squaring, which cannot perform operations in the prime number field, and is not designed for interleaving in polynomial based computations. An additional analysis is made of an approach to use the extension field in polynomial based arithmetic in Paar, C., F. Fleischmann and P. Soria-Rodriguez, “Fast Arithmetic for Public-Key Algorithms in Galois Fields with Composite Exponents”, IEEE Transactions on Computers, vol. 48, No. 10, October 1999, henceforth “Paar”. W. Wesley Peterson and E. J. Weldon Jr., in the second edition of “Error-Correcting Codes”, published by the MIT Press, Cambridge, Mass., 1972, pages 174-179, demonstrated circuits for performing division in the polynomial based residual number system GF(2q), hereinafter, “Peterson”. Peterson's circuit can only be used in a device where the multiplier is exactly the length of the modulus. Typically, that would demand a device that would be more than twice as long as present devices, and would not be cost effective for compact implementations. It could not be used in interleaved implementations, and could not be useful where l is longer than 1, as he has not provided an anticipatory device for determining the Y0 of a multibit character.
Whereas, Knuth [D. Knuth, The art of computer programming, vol. 2: Seminumerical algorithms, Addison-Wesley, Reading Mass., 1981] page 407, implies that using an ordinary division process on a single l bit character in polynomial based division, we can assume a method to anticipate the next character in the quotient, this invention discloses a method for anticipating the next character of a quotient deterministically using a logic configuration.